#include <iostream>

using namespace std;

long long cnt = 0;

// hanoi n ΪŲ�����ӵ�����, ���Ӵ��ϵ��±�� 1,2,3,...,n 
// s ΪԴ����   A B C
// d ΪĿ�����ӣ� t Ϊ�������� 
void hanoi(int n, char s, char t, char d) {
	// ��һ�ε���ʱ�β� s = 'A', d = 'C', t = 'B'
	if(n==1) {
		cnt++;
		// cout << "1�����Ӵ�" << s << "Ų����" << d << endl;
		return;		// �ݹ����ֹ���� 
	}	
	// ����1Դ'A', ����3Ŀ��'B', ����2����'C'
	hanoi(n-1, s, d, t);
	// move һ������ n �����ӣ�s==>d 
	cnt++;
	// cout << n << "�����Ӵ�" << s << "Ų����" << d << endl;
	// ����1Դ'B', ����3Ŀ��'C', ����2����'A'
	hanoi(n-1, t, s, d);
}

int main(){
	int n = 3;
	hanoi(n, 'A', 'B', 'C');
	cout << cnt;  // 2^n - 1
	return 0;
} 
